package sol.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Different Ways to Add Parentheses
 */
public class Issue241 {
    public List<Integer> diffWaysToCompute(String input) {

        List<Integer> res = new ArrayList<Integer>();

        for (int i = 0; i < input.length(); ++i) {
            char c = input.charAt(i);
            if (c == '+' || c == '*' || c == '-') {
                String left = input.substring(0, i);
                String right = input.substring(i + 1);
                List<Integer> lvalues = diffWaysToCompute(left);
                List<Integer> rvalues = diffWaysToCompute(right);
                for (int lv : lvalues) {
                    for (int rv : rvalues) {
                        if (c == '+') res.add(lv + rv);
                        if (c == '-') res.add(lv - rv);
                        if (c == '*') res.add(lv * rv);
                    }
                }
            }
        }

        if (res.size() == 0) res.add(Integer.valueOf(input));
        return res;
    }

    public static void main(String[] args) {
        String input = "2*3-4*5";
        Issue241 sol = new Issue241();
        List<Integer> values = sol.diffWaysToCompute(input);
        System.out.println(values);
    }
}
